﻿#include <iostream>
using namespace std;

const int n = 5;							//顶点个数

int arc[n][n] = {							//用邻接矩阵存储顶点之间边的情况
	0, 1, 1, 0, 0,
	1, 0, 1, 1, 1,
	1, 1, 0, 0, 1,
	0, 1, 0, 0, 1,
	0, 1, 1, 1, 0
};

int color[n] = {0};							//存储n个顶点的着色情况

int ok(int k) {                             //判断顶点k的着色是否发生冲突
	for(int i = 0; i < k; i++) {
		if(arc[k][i] == 1 && color[i] == color[k]) {
			return 0;
		}
	}
	return 1;
}

void graphColor(int m) {
	int i, k;
	for(i = 0; i < n; i++) {                //将数组color[n]初始化为0
		color[i] = 0;
	}
	k = 0;                                  //注意数组下标从0开始
	while(k >= 0) {
		color[k] = color[k] + 1;            //去下一种颜色
		while(color[k] <= m) {
			if(ok(k)) {
				break;
			} else {
				color[k] = color[k] + 1;    //搜索下一个颜色
			}
		}
		if(color[k] <= m && k == n - 1) {   //求解完毕，输出解
			for (i = 0; i < n; i++) {
				cout << color[i] << " ";
			}
			return;
		}
		if(color[k] <= m && k < n - 1) {
			k = k + 1;                      //处理下一个顶点
		} else {
			color[k--] = 0;                 //回溯
		}
	}
}

int main() {
	graphColor(4);

	system("pause");
	return 0;
}